package algorithm.tree;

import util.ListUtil;
import util.TreeNode;
import util.TreeUtil;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: 18362
 * @Create: 2022-04-06 2:20:37 星期三
 */
public class TreeIterate {

    private static List<Integer> result = new ArrayList<>();

    public static void preOrder(TreeNode root) {
        if(root==null)
            return;
        result.add(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

    public static void inOrder(TreeNode root) {
        if (root==null)
            return;
        inOrder(root.left);
        result.add(root.val);
        inOrder(root.right);
    }

    public static void postOrder(TreeNode root) {
        if(root == null)
            return;
        postOrder(root.left);
        postOrder(root.right);
        result.add(root.val);
    }

    public static void preOrderIterate(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                result.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            cur = cur.right;
        }
    }

    public static void inOrderIterate(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            result.add(cur.val);
            cur = cur.right;
        }
    }

    public static void postOrderIterate(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root, pre = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.addFirst(cur);
                cur = cur.left;
            }
            cur = stack.getFirst();
            if (cur.right != null && cur.right != pre) {
                cur = cur.right;
            } else {
                result.add(cur.val);
                stack.removeFirst();
                pre = cur;
                cur = null;
            }
        }
    }

    public static void preOrderMorris(TreeNode root) {

    }

    public static void inOrderMorris(TreeNode root) {

    }

    public static void postOrderMorris(TreeNode root) {

    }

    public static void main(String[] args) {
        TreeNode root = TreeUtil.deserialize("[1,2,3,4,5,6,null,null,7]");
        TreeUtil.printPreorder(root);
        TreeUtil.printLevel(root);
        preOrder(root);
//        inOrder(root);
//        postOrder(root);
        preOrderIterate(root);
//        inOrderIterate(root);
//        postOrderIterate(root);
//        preOrderMorris(root);
//        inOrderMorris(root);
//        postOrderMorris(root);
        ListUtil.printIntList(result);
    }
}
